package src.BlueBridge.GreedyStrategyAndDynamicProgramming;

/**
    有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，
    求所有挑选方案中价值总和的最大值
    1<=n<=100
    1<=wi,vi<=100
    1<=W<=10000
    输入:
    n = 4
    (w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
    W = 5
    输出:
    7(选择第0 1 3号物品)

    因为对于每个问题只有选和不选两种情况，所以这个问题称为01背包问题
 */

public class _10_01背包问题 {

    // 重量表
    static int[] w = {2, 1, 3, 2};
    // 价值表
    static int[] v = {3, 2, 4, 2};
    // 物品数量
    static int n = 4;
    // 背包的承重极限
    static int W = 5;

    public static void main(String[] args) {
        int ww = W;
        int ans = dfs(0, W);
        System.out.println(ans);

    }

    // dfs解法
    public static int dfs(int i, int ww) {
        // 装不进去了
        if (ww <= 0)
            return 0;
        // 没有东西可选了
        if (i == n)
            return 0;

        // 不选择当前物品，直接从下一个范围开始选
        int v2 = dfs(i + 1, ww);
        // 如果能装下
        if (ww >= w[i]) {
            // 那就选择当前物品，下一个从i+1开始，承重也下降了
            int v1 = v[i] + dfs(i + 1, ww - w[i]);
            return Math.max(v1, v2);
        }else {
            return v2;
        }
    }

    // dp解法
    public static int dp() {
        // 背包重量要从0开始
        // 横坐标为物品数量(范围)，纵坐标为背包重量
        int[][] dp = new int[n][W + 1];
        // 初始化DP表的第一行
        for (int i = 0 ; i < dp[0].length ; i++) {
            // 如果重量大于等于0号物品
            if (i >= w[0]) {// 每种容量-0号物品
                // 要的起
                dp[0][i] = v[0];
            }else {
                // 要不起
                dp[0][i] = 0;
            }
        }
        // 其他行(从第二行开始遍历起，因为第一行已经被赋值完毕)
        for (int i = 1 ; i < dp.length ; i++) {
            // j是列，也是这一次装载需要到上一行查找的背包剩余容量
            for (int j = 0 ; j < dp[0].length ; j++) {
                if (j >= w[i]) {// 要的起
                    // 选择当前物品也即第i号物品，剩余的容量
                    int i1 = v[i] + dp[i - 1][j - w[i]];
                    // 不选
                    int i2 = dp[i - 1][j];
                    // 取两者最大值
                    dp[i][j] = Math.max(i1, i2);
                }else {// 要不起
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][W];
    }
}
